/////////////////////////////////////////////////////////////////////////////
/// @file AvlTree.hpp
/// @ingroup
///
/// File containing the implementation of AVL tree
///
/// @see: BiTree.hpp
///
/// @if REVISION_HISTORY_INCLUDED
/// @par Edit History
/// @li [0]        zhalat 18-Aug-2014 Initial revision of file.
/// @endif
///
/// @par &copy;  2014 HalSoft
/////////////////////////////////////////////////////////////////////////////

#ifndef AVLTREE_HPP_
#define AVLTREE_HPP_

//***************************************************************************
// C L A S S 'S   I N T E R F A C E
//***************************************************************************
/*
 *   private:
 1.  RR_rot( BTNode<parAvlTree> *pNode );
 2.  LL_rot( BTNode<parAvlTree> *pNode );
 3.  RL_rot( BTNode<parAvlTree> *pNode );
 4.  LR_rot( BTNode<parAvlTree> *pNode );
*/

// SYSTEM INCLUDES
#include <vector>
#include <assert.h>

// C++ PROJECT INCLUDES
#include "BiTree.hpp"

//forward reference
class AvlTree_TestSuite;

namespace tree
{
    enum rotation{
        NONE,
        RR,
        LL,
        RL,
        LR
    };


    template <class parAvlTree>
    class AvlTree : protected BiTree<parAvlTree>
    {
        public:

        private:
            bool RR_rot( BTNode<parAvlTree> *pNode );
            bool LL_rot( BTNode<parAvlTree> *pNode );
            bool RL_rot( BTNode<parAvlTree> *pNode );
            bool LR_rot( BTNode<parAvlTree> *pNode );
            BTNode<parAvlTree>* ins( const parAvlTree &data, BTNode<parAvlTree>* pos = NULL );
            enum rotation rot( BTNode<parAvlTree>*const pos );

        //make our private data available for test
        friend class ::AvlTree_TestSuite;
    };

    /** @brief:        AVL tree - RR rotate.
     *                 As an input is given ptr to subtree which should be balanced.
     *                 The output is balanced subtree.
        @see:         LL_rot, LR_rot, RL_rot
                    more: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/mp002.php
        @param1:     root of subtree
        @return:     true if OK
    */
    template <class parAvlTree>
    bool AvlTree<parAvlTree>::RR_rot( BTNode<parAvlTree> *pNode )
    {//pNode++;
        using namespace std;
        BTNode<parAvlTree> **pptempUpA_s,**pptempAR_s, **pptempBL_s;
        BTNode<parAvlTree> *ptempA_d,  *ptempB_d, *ptempBL_d;

        //verify preconditions for RR rotate and if OK set appropriate bt value:
        if( NULL == pNode ) {
            return false;
        }
        else if ( (-2 == pNode->bt) && (0 == pNode->pRight->bt) ){
            pNode->bt = -1;
            pNode->pRight->bt = 1;
        }
        else if ( (-2 == pNode->bt) && (-1 == pNode->pRight->bt) ){
            pNode->bt = 0;
            pNode->pRight->bt = 0;
        }
        else{
            return false;
        }

        //set appropriate pptempx source pointers:
        if( NULL == pNode->pup )
            pptempUpA_s = &this->pRoot;
        else if (pNode->pup->pRight == pNode)
            pptempUpA_s = &pNode->pup->pRight;
        else if(pNode->pup->pLeft == pNode)
            pptempUpA_s = &pNode->pup->pLeft;
        else return false; //sth. went wrong

        pptempAR_s = &pNode->pRight;
        pptempBL_s = &pNode->pRight->pLeft;

        //set appropriate ptempx destination pointers:
        ptempA_d  = pNode;
        ptempB_d  = pNode->pRight;
        ptempBL_d = pNode->pRight->pLeft;

        //mysterious mixing pointers according RR algo. of avl tree:
        /*  source:        destination:
         *  pptempUpA_s -> ptempB_d
         *  pptempAR_s  -> ptempBL_d
         *  pptempBL_s  -> ptempA_d
         */

        *pptempUpA_s = ptempB_d;
        ptempB_d->pup = pNode->pup;

        *pptempAR_s = ptempBL_d;
        if( NULL != ptempBL_d)     //prevent NULL dereference
            ptempBL_d->pup = ptempA_d;

        *pptempBL_s = ptempA_d;
        ptempA_d->pup = ptempB_d;

        return true;
    }

    /** @brief:        AVL tree - LL rotate.
     *                 As an input is given ptr to subtree which should be balanced.
     *                 The output is balanced subtree.
        @see:         RR_rot, LR_rot, RL_rot
                    more: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/mp002.php
        @param1:     root of subtree
        @return:     true if OK
    */
    template <class parAvlTree>
    bool AvlTree<parAvlTree>::LL_rot( BTNode<parAvlTree> *pNode )
    {
        using namespace std;
        BTNode<parAvlTree> **pptempUpA_s,**pptempAL_s, **pptempBR_s;
        BTNode<parAvlTree> *ptempA_d,  *ptempB_d, *ptempBR_d;

        //verify preconditions for LL rotate and if OK set appropriate bt value:
        if( NULL == pNode ) {
            return false;
        }
        else if ( (2 == pNode->bt) && (0 == pNode->pLeft->bt) ){
            pNode->bt = 1;
            pNode->pLeft->bt = -1;
        }
        else if ( (2 == pNode->bt) && (1 == pNode->pLeft->bt) ){
            pNode->bt = 0;
            pNode->pLeft->bt = 0;
        }
        else{
            return false;
        }

        //set appropriate pptempx source pointers:
        if( NULL == pNode->pup )
            pptempUpA_s = &this->pRoot;
        else if (pNode->pup->pRight == pNode)
            pptempUpA_s = &pNode->pup->pRight;
        else if(pNode->pup->pLeft == pNode)
            pptempUpA_s = &pNode->pup->pLeft;
        else return false; //sth. went wrong

        pptempAL_s = &pNode->pLeft;
        pptempBR_s = &pNode->pLeft->pRight;

        //set appropriate ptempx destination pointers:
        ptempA_d  = pNode;
        ptempB_d  = pNode->pLeft;
        ptempBR_d = pNode->pLeft->pRight;

        //mysterious mixing pointers according LL algo. of avl tree:
        /*  source:        destination:
         *  pptempUpA_s -> ptempB_d
         *  pptempAL_s  -> ptempBR_d
         *  pptempBR_s  -> ptempA_d
         */

        *pptempUpA_s = ptempB_d;
        ptempB_d->pup = pNode->pup;

        *pptempAL_s = ptempBR_d;
        if( NULL != ptempBR_d)     //prevent NULL dereference
            ptempBR_d->pup = ptempA_d;

        *pptempBR_s = ptempA_d;
        ptempA_d->pup = ptempB_d;

        return true;
    }

    /** @brief:        AVL tree - RL rotate.
     *                 As an input is given ptr to subtree which should be balanced.
     *                 The output is balanced subtree.
        @see:         RR_rot, LR_rot, LL_rot
                    more: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/mp002.php
        @param1:     root of subtree
        @return:     true if OK
    */
    template <class parAvlTree>
    bool AvlTree<parAvlTree>::RL_rot( BTNode<parAvlTree> *pNode )
    {
        using namespace std;
        BTNode<parAvlTree> **pptempUpA_s, **pptempAR_s, **pptempBL_s, **pptempCL_s, **pptempCR_s ;
        BTNode<parAvlTree> *ptempA_d,  *ptempB_d, *ptempC_d, *ptempCL_d, *ptempCR_d;

        //verify preconditions for RL rotate and if OK set appropriate bt value:
        if( NULL == pNode ) {
            return false;
        }
        else if ( (-2 == pNode->bt) && (1 == pNode->pRight->bt) && (-1 == pNode->pRight->pLeft->bt) ){
            pNode->bt = 1;
            pNode->pRight->bt = 0;
            pNode->pRight->pLeft->bt = 0;
        }
        else if ( (-2 == pNode->bt) && (1 == pNode->pRight->bt) && (0 == pNode->pRight->pLeft->bt) ){
            pNode->bt = 0;
            pNode->pRight->bt = 0;
            pNode->pRight->pLeft->bt = 0;
        }
        else if ( (-2 == pNode->bt) && (1 == pNode->pRight->bt) && (1 == pNode->pRight->pLeft->bt) ){
            pNode->bt = 0;
            pNode->pRight->bt = -1;
            pNode->pRight->pLeft->bt = 0;
        }
        else{
            return false;
        }

        //set appropriate pptempx source pointers:
        if( NULL == pNode->pup )
            pptempUpA_s = &this->pRoot;
        else if (pNode->pup->pRight == pNode)
            pptempUpA_s = &pNode->pup->pRight;
        else if(pNode->pup->pLeft == pNode)
            pptempUpA_s = &pNode->pup->pLeft;
        else return false; //sth. went wrong

        pptempAR_s = &pNode->pRight;
        pptempBL_s = &pNode->pRight->pLeft;
        pptempCL_s = &pNode->pRight->pLeft->pLeft;
        pptempCR_s = &pNode->pRight->pLeft->pRight;

        //set appropriate ptempx destination pointers:
        ptempA_d = pNode;
        ptempB_d = pNode->pRight;
        ptempC_d = pNode->pRight->pLeft;
        ptempCL_d = pNode->pRight->pLeft->pLeft;
        ptempCR_d = pNode->pRight->pLeft->pRight;

        //mysterious mixing pointers according RL algo. of avl tree:
        /*  source:        destination:
         *  pptempUpA_s -> ptempC_d
         *  pptempAR_s  -> ptempCL_d
         *  pptempBL_s  -> ptempCR_d
         *  pptempCL_s  -> ptempA_d
         *  pptempCR_s  -> ptempB_d
         */

        *pptempUpA_s = ptempC_d;
        ptempC_d->pup = pNode->pup;
        *pptempAR_s = ptempCL_d;
        if( NULL != ptempCL_d )     //prevent NULL dereference
            ptempCL_d->pup = pNode;
        *pptempBL_s = ptempCR_d;
        if( NULL != ptempCR_d )     //prevent NULL dereference
            ptempCR_d->pup = ptempB_d;
        *pptempCL_s = ptempA_d;
        ptempA_d->pup = ptempC_d;
        *pptempCR_s = ptempB_d;
        ptempB_d->pup = ptempC_d;

        return true;
    }

    /** @brief:        AVL tree - LR rotate.
     *                 As an input is given ptr to subtree which should be balanced.
     *                 The output is balanced subtree.
        @see:         RR_rot, RL_rot, LL_rot
                    more: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/mp002.php
        @param1:     root of subtree
        @return:     true if OK
    */
    template <class parAvlTree>
    bool AvlTree<parAvlTree>::LR_rot( BTNode<parAvlTree> *pNode )
    {
        using namespace std;
        BTNode<parAvlTree> **pptempUpA_s, **pptempAL_s, **pptempBR_s, **pptempCL_s, **pptempCR_s;
        BTNode<parAvlTree> *ptempA_d,  *ptempB_d, *ptempC_d, *ptempCL_d, *ptempCR_d;

        //verify preconditions for RL rotate and if OK set appropriate bt value:
        if( NULL == pNode ) {
            return false;
        }
        else if ( (2 == pNode->bt) && (-1 == pNode->pLeft->bt) && (-1 == pNode->pLeft->pRight->bt) ){
            pNode->bt = 0;
            pNode->pLeft->bt = 1;
            pNode->pLeft->pRight->bt = 0;
        }
        else if ( (2 == pNode->bt) && (-1 == pNode->pLeft->bt) && (0 == pNode->pLeft->pRight->bt) ){
            pNode->bt = 0;
            pNode->pLeft->bt = 0;
            pNode->pLeft->pRight->bt = 0;
        }
        else if ( (2 == pNode->bt) && (-1 == pNode->pLeft->bt) && (1 == pNode->pLeft->pRight->bt) ){
            pNode->bt = -1;
            pNode->pLeft->bt = 0;
            pNode->pLeft->pRight->bt = 0;
        }
        else{
            return false;
        }

        //set appropriate pptempx source pointers:
        if( NULL == pNode->pup )
            pptempUpA_s = &this->pRoot;
        else if (pNode->pup->pRight == pNode)
            pptempUpA_s = &pNode->pup->pRight;
        else if(pNode->pup->pLeft == pNode)
            pptempUpA_s = &pNode->pup->pLeft;
        else return false; //sth. went wrong

        pptempAL_s = &pNode->pLeft;
        pptempBR_s = &pNode->pLeft->pRight;
        pptempCL_s = &pNode->pLeft->pRight->pLeft;
        pptempCR_s = &pNode->pLeft->pRight->pRight;

        //set appropriate ptempx destination pointers:
        ptempA_d = pNode;
        ptempB_d = pNode->pLeft;
        ptempC_d = pNode->pLeft->pRight;
        ptempCL_d = pNode->pLeft->pRight->pLeft;
        ptempCR_d = pNode->pLeft->pRight->pRight;

        //mysterious mixing pointers according RL algo. of avl tree:
        /*  source:        destination:
         *  pptempUpA_s -> ptempC_d
         *  pptempAL_s  -> ptempCR_d
         *  pptempBR_s  -> ptempCL_d
         *  pptempCL_s  -> ptempB_d
         *  pptempCR_s  -> ptempA_d
         */

        *pptempUpA_s = ptempC_d;
        ptempC_d->pup = pNode->pup;
        *pptempAL_s = ptempCR_d;
        if( NULL != ptempCR_d )     //prevent NULL dereference
            ptempCR_d->pup = pNode;
        *pptempBR_s = ptempCL_d;
        if( NULL != ptempCL_d )     //prevent NULL dereference
            ptempCL_d->pup = ptempB_d;
        *pptempCR_s = ptempA_d;
        ptempA_d->pup = ptempC_d;
        *pptempCL_s = ptempB_d;
        ptempB_d->pup = ptempC_d;

        return true;
    }

    /** @brief:        AVL tree - insert data into the tree.
     *                 Note: Method provides appropriate rotate to keep
     *                 tree as short as possible according to AVL tree spec.
        @param1:     data to be inserted into the tree.
        @param2:     current comparable node(position) in the tree.
                    NOTE: user shall not use this parameter in normal usage.
        @return:     if succeed - pointer to inserted data.
                    Null - data wasn't inserted (fail) or currently exists in the tree.
    */
    template <class parAvlTree>
    BTNode<parAvlTree>* AvlTree<parAvlTree>::ins( const parAvlTree &data, BTNode<parAvlTree>* pos )
    {
        BTNode<parAvlTree>* temp;

        //empty tree - just put new data and exit
        if( 0==this->msize ){
            temp = this->ins_left( NULL, data);
            temp->bt = 0;
            return temp;
        }

        // pos may be NULL when ins() is called by user (not recursion).
        // in that case it should always point to root node
        if( NULL == pos)
            pos = this->pRoot;

        //try insert data
        if( pos->data<=data && pos->pRight != NULL ){
             temp = this->ins( data, pos->pRight );
        }
        else if( pos->data<=data && pos->pRight == NULL ){
             temp = this->ins_right( pos, data );
             temp->bt = 0;
        }
        else if( pos->data>=data && pos->pLeft != NULL ){
             temp = this->ins( data, pos->pLeft );
        }
        else if ( pos->data>=data && pos->pLeft == NULL ){
             temp = this->ins_left( pos, data );
             temp->bt = 0;
        }
//        else if ( pos->data == data ){
//             temp = NULL;
//        }
        else {
            assert( false ); //change to throw()
        }

       /* if temp == NULL it means node wasn't created.
        *                  theren't necessity change bt of any node. So just exit.
        * if temp != NULL bt must be set and checked.
        */
        if( NULL != temp ){
            //data was added into the tree.

            //firstly - update bt. '+1' due to we measure height of subtree.
            //If for ex. pos->pLeft == NULL as a result we give 0 not -1 as tree_high would like to be.
            int bt_l = this->tree_high( pos->pLeft ) + 1;
            int bt_r = this->tree_high( pos->pRight ) + 1;
            pos->bt = bt_l - bt_r;

            //secondly - check for rotation:
            if ( pos->pLeft == NULL && pos->pRight == NULL ) {
                 /*its impossible. Data was added so there mustn't both pointer be NULL*/
                 assert( false ); //change to throw()
            }
            else /*try if there is necessity performing rotation. If so, do it*/
                rot( pos );
        }
        return temp;
    }

    /** @brief:        Performing rotation from given node.
     *
        @param1:    Pointer to node, from which rotation should be applied
        @return:    Typ of rotation has been applied.
    */
    template <class parAvlTree>
    enum rotation AvlTree<parAvlTree>::rot( BTNode<parAvlTree>*const pos )
    {
        enum rotation eStat;

        if( -2==pos->bt && pos->pRight!=NULL && -1==pos->pRight->bt && true==RR_rot(pos) )
            eStat = RR;
        else if( -2==pos->bt && pos->pRight!=NULL && 0==pos->pRight->bt && true==RR_rot(pos) )
            eStat = RR;
        else if( -2==pos->bt && pos->pRight!=NULL && 1==pos->pRight->bt && true==RL_rot(pos) )
            eStat = RL;
        else if( 2==pos->bt && pos->pLeft!=NULL && -1==pos->pLeft->bt && true==LR_rot(pos) )
            eStat = LR;
        else if( 2==pos->bt && pos->pLeft!=NULL && 0==pos->pLeft->bt && true==LL_rot(pos) )
            eStat = LL;
        else if( 2==pos->bt && pos->pLeft!=NULL && 1==pos->pLeft->bt && true==LL_rot(pos) )
            eStat = LL;
        else
            eStat=NONE;

        return eStat;
    }
}
#endif // AVLTREE_HPP_
